The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Broadcasting is the process of transmitting a message from a node to all other nodes in a network. The problem of constructing sparse graphs in which the broadcast could be accomplished in minimum time has been investigated in several papers. However, the proposed graphs may have nodes of high degree that could be unacceptable from a network designer's point of view. In this paper we consider the...
We consider 3 place relations I(X,Z,Y) where X, Y and Z are sets of propositional variables and I(X,Z,Y) stands for the statement "Knowing Z renders X independent of Y". These relations are called graphoids. The theory of graphoids uncovers the axiomatic basis of informational dependencies and ties it to vertex separation in graphs. In this paper we advance towards a characterization of...
CADULA is a graph-based model for describing and monitoring CAD-processes. Today, the design of product consists of several subtasks, which are realized by functions using different and loosely coupled CAD-systems. The functions are not independent, since they commonly design the same product. The dependencies are primarily given by the information flow between the functions, i.e. the data flow between...
It is shown that up to vertex labelling BNLC grammars of bounded nonterminal degree generate the same languages of simple graphs as hyperedge replacement grammars. This does not hold if the vertex labelling is taken into account. Vice versa hyperedge replacement grammars generate the same languages of simple graphs as BNLC grammars of bounded nonterminal degree. Furthermore the generation of loops...
In this paper, we develop a new theory of attribute graph rewriting systems with priorities. This theory provides a very general tool for describing algorithms from classical graph theory, and for algorithms implemented on networks of communicating processors and distributed systems. Moreover, this theory gives an algebraic model which allows us to mathematically prove properties of distributed algorithms.
In this paper, we demonstrate that the set of all hypergraphs of a hyperedge-replacement language that satisfy a so-called compatible property can again be generated by a hyperedge-replacement grammar. Because many familiar graph-theoretic properties like connectedness, k-colorability, planarity, the existence of Eulerian and Hamiltonian paths and cycles, etc. are compatible and compatibility is closed...
The structure of an asynchronous system of processes is described by a labeled hypergraph. It represents both the past and the present of the system. The set of all possible traces is defined by a hypergraph grammar. In the graph, actions and process states are represented by hyperedges. Each hyperedge is connected to some event nodes, some of which are considered to be predecessors of the edge, whereas...
Plex grammars according to [13], generating two-dimensional plex structures, are a generalization of string grammars. In this paper we describe a parser for context free plex grammars. The parser is an extension of Earley's algorithm, which was originally developed for context free string grammars. Our parser is able to recognize not only complete structures generated by a plex grammar but also partial...
The language PROGRESS presented within this paper is the first strongly typed language which is based on the concepts of PROgrammed Graph REwriting SyStems. This language supports a data flow oriented style of programming (by means of attribute equations), an object oriented style of programming (by supporting multiple inheritance and dynamic bind of attribute designators to their value defining equations),...
We consider the problem of producing aesthetically nice drawings of graphs from the complexity point of view. The following questions are immediate: (1) How to formalize in algorithmic terms that a drawing is nice? (2) What are the computational costs for nice drawings? (3) Are there tools to beat the NP-completeness? For (1) we propose grid embeddings of graphs and measure...
In this paper we initiate study of a new poset invariant, the page number, well-known for graphs. Lower and upper bounds are derived and then they are used to evaluate and to bound the exact value of the page number for some families of posets. Several problems are posed.
We consider a generalized version of Steiner's problem in graphs, motivated by the wire routing phase in physical VLSI design: given a connected, undirected distance graph with groups of required vertices and Steiner vertices, find a shortest connected subgraph containing at least one required vertex of each group. We propose two efficient approximation algorithms computing different approximate solutions...
In 1976 Bondy and Chvátal introduced the k-closure Ck(G) of a graph and described an algorithm which constructs it in O(n4) time. We present an algorithm which requires O(n3) time. However, in the average case, Ck(G) is computed by this algorithm for almost all integers k (in the asymptotic sense) with O ≦ k ≦ 2n − 2 in O(n2) time. We next present a parallel algorithm which requires O(n2 log n) time...
A subset FcV of vertices of a digraph G=(V,A) with n vertices and m arcs, is called a feedback vertex set (fvs), if G-F is an acyclic digraph (dag). The main results in this paper are: (1) An O(n2m) simplification procedure is developed and it is shown that the class of digraphs, for which a minimum fvs is determined by this procedure alone, properly contains two classes for which minimum fvs's...
Recent results of Robertson and Seymour show, that every class that is closed under taking of minors can be recognized in $$\mathcal{O}$$ (n3) time. If there is a fixed upper bound on the treewidth of the graphs in the class, i.e. if there is a planar graph not in the class, then the class can be recognized in $$\mathcal{O}$$ (n2) time. However, this result is non-constructive...
This paper describes an algorithm for finding a minimal transitive reduction Gred of a given directed graph G, where Gred means a subgraph of G with the same transitive closure as G but itself not contains a proper subgraph G1 with the same property too. The algorithm uses depth-first search and two graph transformations...
We propose the partially paged binary tree principle (PPbin tree principle, for short) for maintaining binary trees which do not fit into core and hence must be (at least partially) paged on secondary storage. The PPbin tree principle can be applied to balanced as well as unbalanced binary trees. Paging a balanced binary tree results in a balanced external binary tree. However, main advantage of the...
Highly regular graphs can be represented advantageously by some kind of description shorter than the full adjacency matrix; a natural succinct representation is by means of a boolean circuit computing the adjacency matrix as a boolean function. The complexity of the decision problems for several graph-theoretic properties changes drastically when this succinct representation is used to present the...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.